package com.demo.jzoffer2;

import com.demo.domain.ListNode;
import org.junit.Test;

import java.util.HashSet;

/**
 * @author gy
 * @date 2023/01/12
 */
public class Test0206_01 {
    /**
     * 输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
     * 输出：Reference of the node with value = 8
     * 输入解释：相交节点的值为 8 （注意，如果两个列表相交则不能为 0）。
     * 从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。
     * 在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。
     *
     * 注意：
     *
     * 如果两个链表没有交点，返回 null.
     * 在返回结果后，两个链表仍须保持原有的结构。
     * 可假定整个链表结构中没有循环。
     * 程序尽量满足 O(n) 时间复杂度，且仅用 O(1) 内存。
     * @param headA
     * @param headB
     * @return
     */
    ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        //思路分析：判断两个链表是否相交：可以使用hash集合存储链表节点
        HashSet<ListNode> visited = new HashSet<>();
        // 在返回结果后，两个链表仍须保持原有的结构。 所以使用辅助变量
        ListNode tmp = headA;
        // 1、将headA链表加入到hash集合中
        while (tmp != null) {
            visited.add(tmp);
            tmp = tmp.next;
        }
        tmp = headB;
        // 2、判断headB链表的每个元素是否在集合中存在，若找到（第一次）说明两个链表
        // 从此节点开始相交
        while (tmp != null) {
            if (visited.contains(tmp)){
                // 找到即可返回
                return tmp;
            }
            tmp = tmp.next;
        }
        // 3、如果两个链表没有交点，返回 null.
        return null;
    }

    @Test
    public void m1() {
    }

    @Test
    public void m2() {

    }

}
